import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param a int整型一维数组
     * @param n int整型
     * @param K int整型
     * @return int整型
     */
    public int findKth(int[] a, int n, int k) {
        return quickSelect(a, 0, n - 1, n - k);
    }

    private int quickSelect(int[] a, int left, int right, int k) {
        if (left == right) {
            return a[left];
        }

        int pivotIndex = partition(a, left, right);
        if (k == pivotIndex) {
            return a[k];
        } else if (k < pivotIndex) {
            return quickSelect(a, left, pivotIndex - 1, k);
        } else {
            return quickSelect(a, pivotIndex + 1, right, k);
        }
    }

    private int partition(int[] a, int left, int right) {
        int pivotIndex = left + new Random().nextInt(right - left + 1);
        int pivotValue = a[pivotIndex];
        swap(a, pivotIndex, right);
        int storeIndex = left;
        for (int i = left; i < right; i++) {
            if (a[i] < pivotValue) {
                swap(a, storeIndex, i);
                storeIndex++;
            }
        }
        swap(a, storeIndex, right);
        return storeIndex;
    }

    private void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] a = {3, 2, 1, 5, 6, 4};
        int n = a.length;
        int k = 2;
        System.out.println(solution.findKth(a, n, k)); // 输出 5
    }
}
